// 给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。

// 最小的 24 小时制时间是 00:00，而最大的是 23:59。从 00:00 （午夜）开始算起，过得越久，时间越大。

// 以长度为 5 的字符串返回答案。如果不能确定有效时间，则返回空字符串。

//  

// 示例 1：

// 输入：[1,2,3,4]
// 输出："23:41"
// 示例 2：

// 输入：[5,5,5,5]
// 输出：""
//  

// 提示：

// A.length == 4
// 0 <= A[i] <= 9

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution {
public:
    string largestTimeFromDigits(vector<int>& A) {
        sort(A.begin(), A.end(), greater<int>()); // 从大到小排序
        do {
            if (A[0] * 10 + A[1] < 24 && A[2] * 10 + A[3] < 60)
                return string("") + (char)('0'+A[0]) + (char)('0'+A[1]) + ":" + (char)('0'+A[2]) + (char)('0'+A[3]);
        } while (next_permutation(A.begin(), A.end(), greater<int>())); // 全排列
        return "";
    }
};


class Solution_test {
public:
    string largestTimeFromDigits(vector<int>& A) {
        sort(A.begin(), A.end(), greater<int>()); // 从大到小排序
        cout << "A(sort) : ";
        for (auto i : A) {
            cout << i << " ";
        }
        cout << endl;
        do {
            cout << "A(next_permutation) : ";
                for (auto i : A) {
                    cout << i << " ";
                }
                cout << endl;
            if (A[0] * 10 + A[1] < 24 && A[2] * 10 + A[3] < 60) {
                
                return string("") + (char)('0'+A[0]) + (char)('0'+A[1]) + ":" + (char)('0'+A[2]) + (char)('0'+A[3]);
            }
        } while (next_permutation(A.begin(), A.end(), greater<int>())); // 全排列
        return "";
    }
};

int main() {
    vector<int> A{1,2,3,4};
    cout << "A{1,2,3,4} : ";
    for (auto i : A) {
        cout << i << " ";
    }
    cout << endl;
    Solution_test s;
    string res = s.largestTimeFromDigits(A);
    for (auto c : res) {
        cout << c << " ";
    }
    cout << endl;

    return 0;
}

/* run result
A{1,2,3,4} : 1 2 3 4 
A(sort) : 4 3 2 1 
A(next_permutation) : 4 3 2 1 
A(next_permutation) : 4 3 1 2 
A(next_permutation) : 4 2 3 1 
A(next_permutation) : 4 2 1 3 
A(next_permutation) : 4 1 3 2 
A(next_permutation) : 4 1 2 3 
A(next_permutation) : 3 4 2 1 
A(next_permutation) : 3 4 1 2 
A(next_permutation) : 3 2 4 1 
A(next_permutation) : 3 2 1 4 
A(next_permutation) : 3 1 4 2 
A(next_permutation) : 3 1 2 4 
A(next_permutation) : 2 4 3 1 
A(next_permutation) : 2 4 1 3 
A(next_permutation) : 2 3 4 1 
2 3 : 4 1 
*/